#define USING_BUILDIN_STACK_VAR
#include "../common.h"

/*
直接插入排序
*/
void InsertSort(void* array[], int n, int (*compare) (void* c1, void* c2)){
    void* temp;
    for (int i = 1; i < n; i++)
    {
        temp = array[i];
        for (int  j = i - 1; j >= 0; j--)
        {
            if(compare(temp,array[j]) < 0){//默认递增排序，使用 < 而非 <= 保证稳定性
                array[j+1] = array[j]; //比插入元素大的往后移动一个位置
                if(j ==0) array[j] = temp; //插入元素为最小元素
            }else{
                array[j+1] = temp;
                break;
            }
        }
    }
}

/*
 直接插入排序（带哨兵，解决需要判断 j==0 的问题）
 形式参数n仍然计算了哨兵
 */
void InsertSortWithSentry(void *array[], int n, int (*compare) (void* c1, void* c2)){
    for (int i = 1; i < n; i++)
    {
        array[0] = array[i];
        for (int  j = i - 1; j >= 0; j--)
        {
            if(compare(array[0],array[j]) < 0){//默认递增排序，使用 < 而非 <= 保证稳定性
                array[j+1] = array[j]; //比插入元素大的往后移动一个位置
            }else{
                array[j+1] = array[0];
                break;
            }
        }
    }
}

/*
希尔排序
int (*increasement)()为增量序列函数，算法循环调用increasement函数直到其返回0，start参数是预定义的，函数定义者可以自由使用，或者干脆不予理会
待优化：如果总元素过小，步长相对较大，可能会出现数组越界问题
*/
void ShellSort(void *array[], int n, int (*compare) (void* c1, void* c2),int (*increasement)(int start), int start){
    void * temp; //暂存单元
    
    for (int step = increasement(start); step != 0; step = increasement(start)) // x趟直接插入排序，x根据increasement函数来定.
    {
        for (int i = 0; i < step; i++)//对step个子表依次排序
        {
            for (int j = i + step; j < n; j += step) // (i + step) 表明从第i个子表的第二个元素开始插入排序（第一个元素不需要排序）
            {
                temp = array[j];
                //查找插入位置k与移动元素
                int k = j;
                while( (k - step) >= 0 && compare(temp,array[k - step]) < 0){
                    array[k] = array[k - step];
                    k -= step;
                }
                //插入
                array[k] = temp;
            }
            
        }
        
    }
    
    
}


/*
冒泡排序
*/
void swap(void** s1, void** s2){
    void* temp;
    temp = *s2;
    *s2 = *s1;
    *s1 = temp;
}

void BubbleSort(void* array[], int n, int (*compare)(void *c1, void* c2)){
    bool flag;
    for (int i = 0; i < n; i++)
    {
        flag = false;

        for (int j = n-1; j > i; j--)
        {
            if(compare(array[j], array[j - 1]) < 0){
                swap(&array[j], &array[j - 1]);
                flag = true;
            }
        }
        

        if(flag == false){
            return;
        }
    }
    
}


/*
快速排序的递归算法
*/
int partition(void** array, int(*compare)(void* c1, void* c2), int low, int high){
    void* pivot = array[low];//把第一个元素作为划分依据
    while(low < high){
        while(low < high && compare(array[high],pivot) >= 0){
            high--;
        }
        array[low] = array[high];//交换

        while(low < high && compare(array[low],pivot) <= 0){
            low++;
        }
        array[high] = array[low];//交换
    }
    array[low] = pivot;//pivot元素归位
    return low;
}
void QuickSort(void** array, int(*compare)(void* c1, void* c2), int low, int high){
    if(low < high){
        int pivotPosition = partition(array, compare, low, high);
        QuickSort(array, compare, low, pivotPosition - 1);
        QuickSort(array, compare, pivotPosition + 1, high);
    }
}


/*
快速排序的非递归算法
 使用栈保存区间造成先一次性排序完左边的元素，然后再排序右边的元素
 使用队列可以左右串行排序
*/
void QuickSortNonrecursively(void** array, int(*compare)(void* c1, void* c2), int low, int high){
    stack s;
    InitStack(&s);
    s.push(&s,&high);//先push high
    s.push(&s,&low);//后push low

    int backupLow;
    int backupHigh;
    int* pushedLow;
    int* pushedHigh;
    void* pivot;//暂存枢纽元素
    while (!s.IsEmpty(&s)){
        backupLow = low = *(int*)pop(&s);
        backupHigh = high = *(int*)pop(&s);
        pivot = array[low];//选定第一个元素为pivot

        while(low < high){
            while(low < high && compare(array[high],pivot) >= 0){
                high--;
            }
            array[low] = array[high];
            while(low < high && compare(array[low],pivot) <= 0){
                low++;
            }
            array[high] = array[low];
        }
        array[low] = pivot;//pivot元素归位


        //继续对左部排序
        if(backupLow < low-1){
            pushedLow = malloc(sizeof(int));
            *pushedLow = low - 1;
            s.push(&s,pushedLow);//this is truly 'high'

            pushedHigh = malloc(sizeof(int));
            *pushedHigh = backupLow;
            s.push(&s,pushedHigh);//this is truly 'low'
        }

        //继续对右部排序
        if(low+1 < backupHigh){
            pushedHigh = malloc(sizeof(int));
            *pushedHigh = backupHigh;
            s.push(&s,pushedHigh);//this is truly 'high'

            pushedLow = malloc(sizeof(int));
            *pushedLow = low + 1;
            s.push(&s,pushedLow);//this is truly 'low'
        }
    }
    s.FreeStackData(&s);
}